package org.example.leetcode;
import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description:
 * @date: 2021/7/26 23:34
 */
public class LC22 {

    public static void main(String[] args) {
        LC22 lc=new LC22();
        System.out.println(lc.generateParenthesis(2));
    }
    //fixme https://www.bilibili.com/video/BV1x5411j7KN?from=search&seid=14741858381586943750
    //fixme 要分析执行过程  https://www.bilibili.com/video/BV1c54y1S7iN?from=search&seid=14741858381586943750


    /**
     * 	                  ""
     * 			(		           ) 这种情况下就是左边小于右边，要严格的减掉
     * 		((X      ()        ()       ))X    n=1
     * 	(((   (() ()( ())  ()(  ()) ()) )))  n=1.5
     *(((( ((() ((() (()) (()( ()()  ())( ()))   这是左边的那一半       n=2
     * 是类似于树一样的东西，那就用递归嘛
     */
    public List<String> generateParenthesis(int n) {
        Set<String> list=new HashSet<>();
        helper("",0,0,n,list);
        return new ArrayList<>(list);
    }
    private void helper(String curr,int left,int right,int n,Set<String> list){
        if (left==n && right==n ) {
            list.add(curr);
            return;
        }
        //fixme 一开始我就把右半边减掉
        if (left>n || right>n || left<right ) return; // fixme 如果写成 left>right 居然就变成相反了的
        helper(curr+"(",left+1,right,n,list);
        helper(curr+")",left,right+1,n,list);
    }
}
